The present invention relates to a technology of encoding and decoding a leaf or node position of an element in tree-structured information. More particularly, this invention relates to a device and a method of effectively encoding and decoding position information for each of leaves or nodes in any kind of tree-structured information.
The tree-structured data representation is widely used in various fields of information processing. A representative example is a technique of representing retrieval information of a video content, which is used in ISO/IEC FCD 15938-1. Generally, a video content may be constructed in such a hierarchy that it is composed of one or more scenes each of which is composed of one or more shots or other scenes.
The MPEG-7 standard, in order to facilitate retrieval of data in a video content, defines a technique of describing retrieval information showing a feature such as intensity of motions and color histogram added to each shot. In this case, the hierarchy of the video content can be represented by a tree structure as shown in FIG. 1.
In the example shown in FIG. 1, a video content is composed of two scenes #1 and #2 and the scene #1 is composed of five shots #1-1 to #1-5. The scene #2 is composed of a single shot #2-1. Each shot is given retrieval information.
In the shown tree structure, a video content corresponds to a root of the tree and scenes and shots correspond to nodes thereof. The scenes are the first branched nodes, viewed from the root, of the tree hierarchy, which are nodes in the first hierarchical layer. The shots are therefore nodes in the second hierarchical layer. Retrieval information corresponds to a leaf of the tree. Scenes or shots with smaller numerals correspond to preceding scenes or shots in the sequence.
In case there is a desire to collectively store all of retrieval information corresponding to the leaves of the tree structure, it is also necessary to store at the same time position information for each of the retrieval information. In other words, it is needed to add position information specifying that the retrieval information links to which scene number and which shot number. A method of representing position information, which is used in ISO/IEC FCD 15938-1, is as follows:
In the above-mentioned committee draft, all nodes located in hierarchical layers under a certain node are numbered by sequential numbers from 1 and position information for a leaf is represented by listing numbers of all relevant nodes being in a path from the root node to the leaf.
This method is now used to prepare position information for retrieval information #1-3 shown in FIG. 1. In the first hierarchy, the scene #1 to which the retrieval information#1-3 belongs is a leftmost node hanging from a video content corresponding to the root of the tree structure. Therefore, position information in the first hierarchical layer is No. 1.
In the second hierarchy, the shot #1-3 to which the retrieval information #1-3 belongs is the third of left nodes hanging from the scene #1 in a higher hierarchical layer. The position information in the second layer is No. 3. Therefore, the position information of the retrieval information #1-3 is expressed by (1, 3). (More strictly, this information represents positions of relevant nodes. Although the retrieval information corresponds itself to a leaf existing in the third layer in the tree hierarchy, the number of retrieval information for the shot is limited to 1 in the shown case and therefore the position information of the node is used as the position information of the retrieval information. If there is a plurality of leaves, a leaf number is further attached thereto.)
The above-described position information is hereinafter referred to as position information in the absolute addressing mode. This mode can uniquely represent each of all leaf positions.
The number of bits necessary to store position information in the absolute addressing mode for the shown example will be estimated below. To calculate the number of bits necessary to represent all nodes in each layer of the tree hierarchy, it is necessary to determine in advance the maximum number of possibly growing branches. For example, if the first and second hierarchical layers can have each 8 branches from each node, three bits are required to represent each of the nodes in each hierarchical layer.
Therefore, six (6) bits (3 by 2 bits) are needed to store the position information of one leaf. As there are six (6) leaves in the tree structure shown in FIG. 1, thirty six (36) bits (6 by 6) are needed for the shown case. FIG. 2 shows an example of coded position information for all retrieval information shown in FIG. 1 according to the above-described rule.
The above-described prior art method whereby position information for each of leaves or nodes are encoded in the absolute addressing mode, however, involves such aproblem that the number of bits necessary to store position information for leaves or nodes of the tree structure increases as the number of branches of each of hierarchical layers increases. In general, a video content contains a very large number of scenes or shots, i.e., a huge number of possible branches may be produced, making the bit problem more significant and, therefore, can not be ignored.